package com.hdu.other.dp.intervalDp;

public class lc1312 {
        class Solution {
            public int minInsertions(String s) {
                int n = s.length();
                int[][] dp = new int[n][n];
                for (int i = 0; i < n; i++) {
                    for (int j = 0; j < n; j++) {
                        dp[i][j] = -1;
                    }
                }
                return f(s, 0, n - 1, dp);
            }

            int f(String s, int l, int r, int[][] dp) {
                if (l >= r) {
                    return 0;
                }
                if (dp[l][r] != -1) {
                    return dp[l][r];
                }
                if (l + 1 == r) {
                    return s.charAt(l) == s.charAt(r) ? 0 : 1;
                } else {
                    int ans = 0;
                    if (s.charAt(l) == s.charAt(r)) {
                        ans = f(s, l + 1, r - 1, dp);
                    } else {
                        int p1 = f(s, l + 1, r, dp);
                        int p2 = f(s, l, r - 1, dp);
                        ans = Math.min(p1, p2) + 1;
                    }
                    return dp[l][r] = ans;
                }
            }
        }
}
